//
//  86. 分隔链表.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/5/9.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution86 {
    func partition2(_ head: ListNode?, _ x: Int) -> ListNode? {
        let vHead1 = ListNode(-1)
        let vHead2 = ListNode(-1)
        
        var p1: ListNode? = vHead1
        var p2: ListNode? = vHead2
        
        var cur = head
        while cur != nil {
            if cur!.val < x {
                p1?.next = cur
                p1 = p1?.next
            } else {
                p2?.next = cur
                p2 = p2?.next
            }
            cur = cur?.next
        }
        p1?.next = vHead2.next
        p2?.next = nil
        return vHead1.next
    }
    
    static func test(){
        let root: ListNode? = createNode()
        let solution = Solution86()
        let result = solution.partition2(root, 3)
    }
    static func createNode() -> ListNode{
        let node1 = ListNode(1)
        let node2 = ListNode(4)
        let node3 = ListNode(3)
        let node4 = ListNode(2)
        let node5 = ListNode(5)
        let node6 = ListNode(2)
        node1.next = node2
        node2.next = node3
        node3.next = node4
        node4.next = node5
        node5.next = node6
        return node1
    }
}
